package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

/**
 * @author zhangjy
 * @description 二叉树的直径
 * <p>
 * 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度
 * 这条路径可能经过也可能不经过根节点 root 。
 * 两节点之间路径的 长度 由它们之间边数表示。
 * @date 2025/2/26 16:39
 */
public class DiameterOfBinaryTree_543 {

    public static void main(String[] args) {
        // TODO 官解不太明白，再看看其它讲解；同时看下深度优先搜索
    }

    int ans;

    /**
     * 官解
     */
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;

        ans = 1;
        diameter(root);
        // 直径的长度（节点数-1）
        return ans - 1;
    }

    /**
     * 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度
     * 这条路径可能经过也可能不经过根节点 root 。
     * 两节点之间路径的 长度 由它们之间边数表示。
     */
    private int diameter(TreeNode node) {
        if (node == null) return 0;

        int left = diameter(node.left);
        int right = diameter(node.right);
        ans = Math.max(ans, left + right + 1);

        // 该节点最长的路径（包含节点本身）
        return Math.max(left, right) + 1;
    }

}
